⟸ pàgina anterior ⟸

Exercici 3 (Tasca 7).

(P, NP, coNP)

Propietats de tancament de \mathsf{P}, \mathsf{NP} i \mathsf{coNP}

L’objectiu d’aquest exercici és revisar algunes propietats de tancament de \mathsf{P}, \mathsf{NP} i \mathsf{coNP}.

1. (propietat de tancament respecte de la unió) Demostreu les implicacions següents:
   1. Donats A i B a \mathsf{P}, A\cup B\in \mathsf{P}.
      
   2. Donats A i B a \mathsf{NP}, A\cup B\in \mathsf{NP}.
      
   3. Donats A i B a \mathsf{coNP}, A\cup B\in \mathsf{coNP}.
2. (propietat de tancament respecte de la intersecció) Demostreu les implicacions següents:
   1. Donats A i B a \mathsf{P}, A\cap B\in \mathsf{P}.
      
   2. Donats A i B a \mathsf{NP}, A\cap B\in \mathsf{NP}.
      
   3. Donats A i B a \mathsf{coNP}, A\cap B\in \mathsf{coNP}.
3. (propietat de tancament respecte de la concatenació) Demostreu les implicacions següents:
   1. Donats A i B a \mathsf{P}, A\cdot B\in \mathsf{P}.
      
   2. Donats A i B a \mathsf{NP}, A\cdot B\in \mathsf{NP}.
      
   3. Donats A i B a \mathsf{coNP}, A\cdot B\in \mathsf{coNP}.